package uestc.lj.basicPromotion.tree;

/**
 * 利用原树中大量空闲指针的方式遍历二叉树
 * Morris遍历细节：
 * 假设来到当前节点cur，开始时cur来到头节点位置
 * 1）如果cur没有左孩子，cur向右移动(cur = cur.right)
 * 2）如果cur有左孩子，找到左子树上最右的节点mostRight：
 * a.如果mostRight的右指针指向空，让其指向cur， 然后cur向左移动(cur = cur.left)
 * b.如果mostRight的右指针指向cur，让其指向null， 然后cur向右移动(cur = cur.right)
 * 3）cur为空时遍历停止
 *
 * @Author:Crazlee
 * @Date:2021/11/27
 */
public class Code03_MorrisTraversal {
	public static class Node {
		public int value;
		Node left;
		Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static void morris(Node root) {
		if (root == null) {
			return;
		}
		Node cur = root;
		Node mostRight = null;
		while (cur != null) {
			mostRight = cur.left;
			//cur有左孩子
			if (mostRight != null) {
				//找到cur左孩子的最右边节点且第一次遇到当前右节点
				while (mostRight.right != null && mostRight.right != cur) {
					mostRight = mostRight.right;
				}
				//如果是第一次遇见最右边节点
				if (mostRight.right == null) {
					//修改最右边节点
					mostRight.right = cur;
					cur = cur.left;
					continue;
				} else {
					//第二次遇到最右边节点
					mostRight.right = null;
				}
			}
			//cur没有左孩子或者是第二次遇到最右边节点
			cur = cur.right;
		}
	}

	/**
	 * 只有一次直接打印
	 * 有两次只打印第一次
	 *
	 * @param head 根节点
	 */
	public static void morrisPre(Node head) {
		if (head == null) {
			return;
		}
		Node cur = head;
		Node mostRight = null;
		while (cur != null) {
			mostRight = cur.left;
			if (mostRight != null) {
				while (mostRight.right != null && mostRight.right != cur) {
					mostRight = mostRight.right;
				}
				if (mostRight.right == null) {
					mostRight.right = cur;
					System.out.print(cur.value + " ");
					cur = cur.left;
					continue;
				} else {
					mostRight.right = null;
				}
			} else {
				System.out.print(cur.value + " ");
			}
			cur = cur.right;
		}
		System.out.println();
	}

	/**
	 * 只有一次直接打印
	 * 有两次只打印第二次
	 *
	 * @param head 根节点
	 */
	public static void morrisIn(Node head) {
		if (head == null) {
			return;
		}
		Node cur = head;
		Node mostRight = null;
		while (cur != null) {
			mostRight = cur.left;
			if (mostRight != null) {
				while (mostRight.right != null && mostRight.right != cur) {
					mostRight = mostRight.right;
				}
				if (mostRight.right == null) {
					mostRight.right = cur;
					cur = cur.left;
					continue;
				} else {
					mostRight.right = null;
				}
			}
			System.out.print(cur.value + " ");
			cur = cur.right;
		}
		System.out.println();
	}

	/**
	 * 后序
	 *
	 * @param head 根节点
	 */
	public static void morrisPos(Node head) {
		if (head == null) {
			return;
		}
		Node cur = head;
		Node mostRight = null;
		while (cur != null) {
			mostRight = cur.left;
			if (mostRight != null) {
				while (mostRight.right != null && mostRight.right != cur) {
					mostRight = mostRight.right;
				}
				if (mostRight.right == null) {
					mostRight.right = cur;
					cur = cur.left;
					continue;
				} else {
					mostRight.right = null;
					//逆序打印左树的右边界
					printEdge(cur.left);
				}
			}
			cur = cur.right;
		}
		//单独逆序打印整棵树的右边界
		printEdge(head);
		System.out.println();
	}

	/**
	 * 以head为头的树，逆序打印这棵树的右边界
	 *
	 * @param head 根节点
	 */
	public static void printEdge(Node head) {
		Node tail = reverseEdge(head);
		Node cur = tail;
		while (cur != null) {
			System.out.print(cur.value + " ");
			cur = cur.right;
		}
		reverseEdge(tail);
	}

	/**
	 * 相当于单链表指针逆序的操作
	 * @param from 根节点
	 * @return
	 */
	public static Node reverseEdge(Node from) {
		Node pre = null;
		Node next = null;
		while (from != null) {
			next = from.right;
			from.right = pre;
			pre = from;
			from = next;
		}
		return pre;
	}


}
